package com.zrrd.zuo.manacher;

/**
 * @author ywb
 * @Description:
 * @date 2023/5/3 22:26
 */
//最长回文子串
public class Class01_Manacher {


    private String manacher0(String s) {
        if (s.length() < 2) {
            return s;
        }

        // 第一步：预处理，将原字符串转换为新的字符串
        StringBuilder builder = new StringBuilder();
        builder.append("$");
        for (int i = 0; i < s.length(); i++) {
            builder.append("#");
            builder.append(s.charAt(i));
        }
        builder.append("#@");
        String t = builder.toString();

        // 第二步：得到数组 p
        // p[i] 为 s[i] 的回文半径
        int[] p = new int[t.length()];
        // mx 是现有的所有回文子串中，最大的右边界（回文子串不包括 mx）
        int mx = 0;
        // id 是上述 mx 对应回文子串的中心点
        int id = 0;
        // 最长回文子串的长度及其中心位置索引
        int maxLen = -1;
        int maxIndex = -1;
        // 遍历字符串（不用包括两边加上的 $ 和 @）
        for (int i = 1; i < t.length() - 1; i++) {
            // 利用前面的信息更新 p[i]
            p[i] = mx > i? Math.min(p[2 * id - i], mx - i) : 1;
            // 向两边延伸，让 p[i] 达到最大
            while (t.charAt(i + p[i]) == t.charAt(i - p[i])) {
                p[i]++;
            }
            // 更新 id 和 mx
            if (p[i] + i > mx) {
                mx = p[i] + i;
                id = i;
            }
            // 更新 maxLen 和 maxIndex
            if (p[i] - 1 > maxLen) {
                maxLen = p[i] - 1;
                maxIndex = i;
            }
        }

        // 第三步：计算回文字符串的起始索引
        int start = (maxIndex - maxLen) / 2;

        return s.substring(start, start + maxLen);
    }

    public static int manacher(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // "12132" -> "#1#2#1#3#2#"
        char[] str = manacherString(s);
        //当前回文半径
        int[] parr = new int[str.length];
        //当前扩最大的中间位置
        int c = -1;
        // 讲述中：R代表最右的扩成功的位置
        int r = -1;
        int max = Integer.MIN_VALUE;
        for(int i = 0;i < str.length;i++){
            // R第一个违规的位置，i>= R
            // i位置扩出来的答案，i位置扩的区域，至少是多大。
            parr[i] = r > i ?Math.min(parr[2 * c - i], r - i): 1;
            while (i + parr[i] < str.length && i - parr[i] > -1) {
                if (str[i + parr[i]] == str[i - parr[i]])
                    parr[i]++;
                else {
                    break;
                }
            }
            if (i + parr[i] > r) {
                r = i + parr[i];
                c = i;
            }
            max = Math.max(max, parr[i]);
        }
            return  max-1;
//        if(i > r){//i在r外 暴力扩
//            int L = i - 1;
//            int R = i + 1;
//            while (L >= 0 && R < str.length && str[L] == str[R]){
//                L--;
//                R++;
//                parr[i]++;
//            }
//            if(parr[i] + i >= r){
//                r = i + parr[i];
//                c = i;
//            }
//            max = Math.max(max, parr[i]);
//        }else{
//            if(c-(i-c) - parr[c-(i-c)] > c-(r-c)){//i的对称点的回文区域在L...R内
//            parr[i] = parr[c-(i-c)];
//                if(parr[i] + i >= r){
//                    r = i + parr[i];
//                    c = i;
//                }
//                max = Math.max(max, parr[i]);
//            }else if(c-(i-c) - parr[c-(i-c)] < c-(r-c)){//i的对称点的会问区域在L。。R外
//                parr[i] = r - parr[c-(i-c)];
//                if(parr[i] + i >= r){
//                    r = i + parr[i];
//                    c = i;
//                }
//                max = Math.max(max, parr[i]);
//            }else {//i的对称点的回文在l....r上 从r开始比较
//                parr[i] = parr[c-(i-c)];
//                while (i + parr[i] < str.length && i - parr[i] > -1) {
//                    if (str[i + parr[i]] == str[i - parr[i]])
//                        parr[i]++;
//                    else {
//                        break;
//                    }
//                }
//                if(parr[i] + i >= r){
//                    r = i + parr[i];
//                    c = i;
//                }
//                max = Math.max(max, parr[i]);
//            }
//
//        }

    }
    public static char[] manacherString(String s){
        char[] ss = s.toCharArray();
        char[] str = new char[s.length()*2 + 1];
        int index = 0;
        for(int i = 0;i < str.length;i++){
            //偶数为#
            str[i] = (i&1) == 0 ? '#':  ss[index++];
        }
        return str;
    }
    // for test
    public static int right(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = manacherString(s);
        int max = 0;
        for (int i = 0; i < str.length; i++) {
            int L = i - 1;
            int R = i + 1;
            while (L >= 0 && R < str.length && str[L] == str[R]) {
                L--;
                R++;
            }
            max = Math.max(max, R - L - 1);
        }
        return max / 2;
    }

    // for test
    public static String getRandomString(int possibilities, int size) {
        char[] ans = new char[(int) (Math.random() * size) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
        }
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        int possibilities = 5;
        int strSize = 20;
        int testTimes = 5000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            String str = getRandomString(possibilities, strSize);
            if (manacher(str) != right(str)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish");
//        String s = "aaa";
//        int manacher = manacher(s);
//        System.out.println(manacher);
    }

}

